package 链表中环的入口结点;

//给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
public class Solution
{
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        //判断输入
        if(pHead==null)
            return null;
        //定义指针
        ListNode fast=pHead;
        ListNode slow=pHead;
        //判断有没有环,fast走两步，slow走一步，如果相遇，一定有环，否则没有
        while (fast!=null&&fast.next!=null)
        {
            fast=fast.next.next;
            slow=slow.next;
            if (fast==slow)
                break;
        }
        if (fast==null||fast.next==null)//无环的情况
            return null;
        //找到环的入口结点
        //链表首结点到环入口结点的距离a=(n-1)r+(L-a-x)相遇点到入口结点的距离
        //(n-1)r可以被r整除，r是环的长度
        //分别在链表首结点和相遇点设置指针
        slow=pHead;//拨回首结点
        while (slow!=fast)
        {
            slow=slow.next;
            fast=fast.next;
        }
        return fast;
    }
}
